1398C Good Subarrays | Actinoi's Blog

1398C Good Subarrays

题目链接：Good Subarrays

**题目大意：**给定一个字符串，需要找到有多少个区间使得其区间内每个元素的和为区间长度。

题解：

其区间内每个元素的和为区间长度， 也就是 区间和 = 区间长。

区间和可以用前缀和来维护，因此，可以得到：

移向，可以得到：

统计 ，如果出现重复的，那么 ，因此 可以与前面的所有项组合。

特别需要注意的，当 时，那么， 区间和也就等于区间长度，因此 。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
long long sum[1000001], appear[1000001]; //记录前缀和， 记录出现过几次
int main() {
    long long t, n, ans = 0;
    scanf("%lld", &t);
    while (t >= 1) {
      	t--;
        memset(sum, 0, sizeof(sum));
        memset(appear, 0, sizeof(appear));
        appear[100000] = 1; //注意避免 sum[i] - i 越界！因此，把 100000 作为起点
        ans = 0;
        scanf("%lld", &n);
        char c;
        for (long long i = 1; i <= n; i++) {
            cin >> c;
            sum[i] = sum[i - 1] + c - '0'; //前缀和
            ans = ans + appear[sum[i] - i + 100000]; 
            appear[sum[i] - i + 100000]++; //更新答案
        }
        printf("%lld\n", ans);
    }
    return 0;
}